class Solution {
public:
    vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
        int hsize = heights.size();
        int qsize = queries.size();
        vector<int> ret(qsize,-1);
        vector<int> dp(hsize,-1);
        map<pair<int,int> ,int> rename;
       for (int i = hsize - 2; i >= 0; i--)
       {
           int tmp = i + 1; // 右侧
           while (heights[tmp] <= heights[i]) {   // 找大
               tmp = dp[tmp];
               if (tmp == -1)   break;
           }
           dp[i] = tmp;
       }
        // for(auto e : dp){
        //     cout <<e <<' ';
        // }
        for(int i = 0; i <qsize;i++){
            int maxnum = queries[i][0];
            int minnum = queries[i][1];
            if(maxnum < minnum) swap(maxnum,minnum);
            if(rename[{maxnum,minnum}] != 0){
                ret[i] = rename[{maxnum,minnum}];
                continue;
            }
            if(maxnum == minnum || heights[minnum] < heights[maxnum]) {
                ret[i] = maxnum;
                continue;
            }
            int tmp = maxnum;
            while(tmp != -1){
                if(heights[tmp] > heights[minnum])
                {
                    break;
                }
                tmp = dp[tmp];
            }
            ret[i] = tmp;
            rename[{maxnum,minnum}] = tmp;
        }
        return ret;
    }
};